package com.shiguiwu.springmybatis.algorithm.tree;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @description: 利用哈夫曼树，进行字符串压缩，称哈夫曼编码
 * @author: stone
 * @date: Created by 2023/1/17 21:40
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.tree
 * todo 有问题的代码
 */
@Slf4j
public class HuffmanCode {

    //示例： Make progress every day, and you are your best
    public static void main(String[] args) {
        String content = "Make progress every day, and you are your best1";

        //Map<Byte, Integer> map = stringToMap(content.getBytes());
        //map.forEach((k, v) -> {
        //    byte b= k;
        //    char c = (char) b;
        //    log.info("{} ==> {}", c, v);
        //});
        Node root = stringToHuffmanTree(content.getBytes());

        //root.preOrder();
        Map<Byte, String> byteStringMap = huffmanTreeToHuffmanCode(root);

        byte[] bytes = content.getBytes();
        byte[] result = huffmanCompress(bytes);
        //
        //log.info("压缩率为 ===> {}%", ((double) (bytes.length - result.length) / bytes.length)*100);


        //String s = Integer.toBinaryString(-88);
        //log.info("转成的字符串是 ==> {}",s);

        byte[] bytes1 = huffmanDecompress(result, byteStringMap);

        log.info("还原字符串 ===> {}",new String(bytes1));
    }


    /**
     * 将字符串转成字符和个数的映射关系
     * 例如：a -> 5,b -> 6,c -> 1
     * 要转成asc码
     * @param content
     * @return
     */
    public static Map<Byte, Integer> stringToMap(byte[] content) {

        Map<Byte, Integer> map = new HashMap<>();

        for (byte b : content) {
            map.put(b, map.getOrDefault(b, 0) + 1);

        }

        return map;
    }


    /**
     * 把字符串出现的次数作为二叉树的权重，树上的数据data是字符本身。
     * 形成一个赫夫曼树
     * @param content
     * @return
     */
    public static Node stringToHuffmanTree(byte[] content) {
        Map<Byte, Integer> map = stringToMap(content);
        List<Node> nodes = new ArrayList<>();
        map.forEach((k,v) -> nodes.add(new Node(v, k)));



        while (nodes.size() > 1) {
            Collections.sort(nodes);
            //log.info("转成node list ===> {}", nodes);

            //左节点
            Node l = nodes.get(0);
            //右节点
            Node r = nodes.get(1);

            Node parent = new Node(l.val + r.val, null);
            parent.setLeft(l);
            parent.setRight(r);
            //移除list元素
            nodes.remove(l);
            nodes.remove(r);

            //将parent加到list
            nodes.add(parent);
        }

        return nodes.get(0);

    }

    /**
     * 总方法，传一个字符串或者是一个文件值了，压缩
     * @param content 待压缩的内容
     */
    public static  byte[] huffmanCompress(byte[] content) {
        //1，获取赫夫曼树
        Node root = stringToHuffmanTree(content);
        //2，对应的赫夫曼编码(根据 赫夫曼树)
        Map<Byte, String> map = huffmanTreeToHuffmanCode(root);
        //3，根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
       return compress(content, map);
    }


    /**
     * 解压，转成源来的字节数组
     * @param content 待解压的内容
     * @param map 映射表
     * @return
     */
    public static  byte[] huffmanDecompress(byte[] content, Map<Byte, String> map) {
        //反向映射
        Map<String, Byte> stringByteMap = map.entrySet()
                .stream()
                .collect(Collectors.toMap(e -> e.getValue(), x -> x.getKey(), (o, n) -> n));

        //数字转成字符串
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < content.length; i++) {
            boolean f = i == content.length - 1;
            sb.append(byteToStr(!f, content[i]));
        }
        log.info("得到的字符串为 ===> {}", sb.toString());


        // 3.创建用于存放 byte的集合
        List<Byte> list = new ArrayList<>();
        // 其中 i 在这里充当索引，用于扫描 stringBuilder
        for (int i = 0; i < sb.length();) {
            int count = 1;// 微型计算器，用于记录内部的 while循环,与 i相辅相成
            boolean flag = true;// 用于控制 while
            Byte b = null;// 记录要存放的字节

            while(flag) {
                // 1010100010111...
                // 递增的取出 key 1 ,没有再移动 10  ，101 以此类推
                String key = sb.substring(i,i+count);// i不动，count移动，指定匹配到一个字符(0或1)
                b = stringByteMap.get(key);
                if(b == null) {
                    // 说明没有匹配到
                    count++;
                }else {
                    // 匹配到
                    flag = false;
                }
            }
            list.add(b);
            i += count; // i 直接移动到 count(若 while 中 符合条件的次数 count 达到则 退出，次数 i也没必要移动，此处 i才是辅助)
        }

        // 4.以上循环结束后，说明已经解码结束
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < list.size(); i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }

    private static String byteToStr(boolean f, byte b) {

        // 将 b 转成 int
        int temp = b;
        // 若是正数，则需要补高位,转换需要 int 类型
        if(f) {
            // 按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
            temp |=256;
        }
        // 返回的是 temp 对应的二进制补码
        String str = Integer.toBinaryString(temp);
        if(f) {
            return str.substring(str.length()-8);
        }
        // 若不是正数直接返回
        return str;

    }

    /**
     *
     * @param content 原始数据
     * @param map 映射表
     * @return 压缩后的数据
     */
    private static byte[] compress(byte[] content, Map<Byte, String> map) {
        //1，先将原始的数据转成一整串字符串
        StringBuilder sb = new StringBuilder();
        for (byte b : content) {
            sb.append(map.get(b));
        }

        log.info("原始的字符编码是 ==> {}", sb.toString());

        int len;
        boolean flag = false;
        int length = sb.length();
        int i = length % 8;
        String tail = "";
        if(i==0) {
            len = length/8;
        }else {
            flag = true;
            len = length/8+1;
            tail = sb.substring(length - i);
        }

        byte[] result = new byte[len];

        int index = 0;
        for (int j = 0; j < length -i; j+=8) {
            result[index] = (byte)Integer.parseInt(sb.substring(j,j+8), 2);
            index++;
        }

        if (flag) {
            result[len-1] =  (byte)Integer.parseInt(tail, 2);
        }
        return result;
    }


    /**
     * 传入一个赫夫曼树，然后将对应的叶子节点，转成字符串和赫夫曼编码映射关系
     * @param root 赫夫曼树
     */
    public static Map<Byte, String>  huffmanTreeToHuffmanCode(Node root) {
        Map<Byte, String> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        getHuffmanCode("0", map,(Node) root.left, sb);
        getHuffmanCode("1", map,(Node) root.right, sb);

        //log.info("map ==> {}", map);
        return map;
    }



    public static void getHuffmanCode(String code, Map<Byte, String> map, Node node,StringBuilder builder) {
        StringBuilder sb = new StringBuilder(builder);
        sb.append(code);

        if (node == null) {
            return;
        }
        if (node.data == null) {
            getHuffmanCode("0", map,(Node) node.left,sb);
            getHuffmanCode("1", map,(Node) node.right,sb);

        }

        else {
            map.put(node.data, sb.toString());
        }


    }


    @Data
    public static class Node extends HuffmanTree.Node {
        private Byte data;

        public Node(Integer val, Byte data) {
            super(val);
            this.data = data;
        }


        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", val=" + val +
                    '}';
        }
    }






}
